package day_2022_9_to_12.Day;

import java.util.*;

/**
 * @author haomin
 * @date 2022/09/18 18:06
 **/
public class Day16_1_Num827_LargestIsland {
    class Solution {
        int[] d = {0, -1, 0, 1, 0};

        public int largestIsland(int[][] grid) {
            int n = grid.length, res = 0;
            int[][] tag = new int[n][n];
            Map<Integer, Integer> area = new HashMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1 && tag[i][j] == 0) {
                        int t = i * n + j + 1;
                        area.put(t, dfs(grid, i, j, tag, t));
                        res = Math.max(res, area.get(t));
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 0) {
                        int z = 1;
                        Set<Integer> connected = new HashSet<Integer>();
                        for (int k = 0; k < 4; k++) {
                            int x = i + d[k], y = j + d[k + 1];
                            if (!valid(n, x, y) || tag[x][y] == 0 || connected.contains(tag[x][y])) {
                                continue;
                            }
                            z += area.get(tag[x][y]);
                            connected.add(tag[x][y]);
                        }
                        res = Math.max(res, z);
                    }
                }
            }
            return res;
        }

        public int dfs(int[][] grid, int x, int y, int[][] tag, int t) {
            int n = grid.length, res = 1;
            tag[x][y] = t;
            for (int i = 0; i < 4; i++) {
                int x1 = x + d[i], y1 = y + d[i + 1];
                if (valid(n, x1, y1) && grid[x1][y1] == 1 && tag[x1][y1] == 0) {
                    res += dfs(grid, x1, y1, tag, t);
                }
            }
            return res;
        }

        public boolean valid(int n, int x, int y) {
            return x >= 0 && x < n && y >= 0 && y < n;
        }
    }
}